import random
from typing import List
from collections import Counter

def quicksort(cnt_nums, k):
    _, p = random.choice(cnt_nums) # 基准值取随机元组的value部分
    # 遍历分区
    small, equal, big = [], [], []
    for x, c in cnt_nums:
        if c < p:
            small.append((x, c))
        elif c > p:
            big.append((x, c))
        else:
            equal.append((x, c))
    # 判断条件
    if len(big) == k:
        return big
    elif len(big) + len(equal) == k:    # 容易漏这种情况
        return big + equal
    elif len(big) > k:
        return quicksort(big, k)
    else:           
        return big + quicksort(small+equal, k-len(big))

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # topK问题，使用quicksort方法，or 堆排序
        # quicksort：当big区间长度==k时，返回big列表
        cnt_nums = Counter(nums)    # 字典{1:3, 2:2, 3:1}
        cnt_nums = list(cnt_nums.items())   # 转换为列表[(1,3), (2,2), (3,1)]
        top_k = quicksort(cnt_nums, k)  # 得到列表元组[[1,3],[2,2]]
        return [item[0] for item in top_k]
